package cn.pugle.oj.leetcode;

import cn.pugle.oj.catalog.Greedy;

import java.util.ArrayList;
import java.util.Collections;
import java.util.List;

/**
 * 切分子串, so that each letter appears in at most one part,
 * 也就是说多个part之间没有相同字母
 * 尽量多切
 * <p>
 * solution给的扫描两边, 用空间换时间,
 * https://leetcode.com/problems/partition-labels/solution/
 * <p>
 * 和之前另一道贪心题目392里大神的优化相似
 * https://www.bilibili.com/video/BV1aW411m79s
 * 14:20
 *
 * @author tzp
 * @since 2020/10/17
 */
public class LC763 implements Greedy {
    public List<Integer> partitionLabels(String S) {
        if (S == null || S.length() == 0) return Collections.emptyList();
        int curPartStart = 0, curPartEnd = 0;
        List<Integer> parts = new ArrayList<>();
        for (int i = 0; i < S.length(); i++) {
            char c = S.charAt(i);
            int nextEnd = S.indexOf(c, curPartEnd + 1);
            if (nextEnd >= 0) {
                curPartEnd = nextEnd;
            }
            if (i == curPartEnd) {
                parts.add(curPartEnd - curPartStart + 1);
                curPartStart = curPartEnd + 1;
                curPartEnd = curPartEnd + 1;
            }
        }
        return parts;
    }

    public static void main(String[] args) {
        System.out.println(new LC763().partitionLabels("ababcbacadefegdehijhklij"));
    }
}
